package com.Algorithm.Study.ThinkTest;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/07/8:48
 * @Description: 利用递归法进行归并排序
 * @Target: 归并排序---递归(树)+指针游走排序
 */
public class MergeSortTest {

    // 解---由大到小解决,
    // 1.解递归
  // 0,R都是数组下标
    public void process(int arr[],int L,int R){
        if(L==R){   // 结束标志,也就是叶子节点结束
            return;
        }
        int m = L+((R-L)>>1);
        process(arr,L,m);            //----L----m-----R--  不仅仅一个,是树
        process(arr,m+1,R);
       /* System.out.println("递归流程"+":"+L + "--" + R);*/
        merge(arr,L,m,R);


    }

    // 2.解排序--按照最基本的叶子进行计算,满足最基本的LMR的叶子进行思考,如 529


    public void merge(int arr[],int L,int M,int R){
        // 定:要使得两边有序 ---
        // 解:最基本的叶子,最基础的92  次级 29 35 (进来的元素在之前都做过处理) ---
        // 需求:指针,[L,M]边的,[M,R]边的
        int p1 = L; // 左边的指针
        int p2 = M+1; // 中间的指针
        // 辅助数组存值
        int help[] = new int[R-L+1];   // 空的
        int i = 0; // 辅助的指针
        // 节点卡标
        while (p1 <= M && p2 <= R){ // 有一个指针满足就停止
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];  // 此时必定会将一边的全打进去
        }


        while (p1 <= M){
            help[i++] = arr[p1++];
        }

        while (p2 <= R){
            help[i++] = arr[p2++];
        }

        for (int j = 0; j < help.length; j++) {
            arr[L+j] = help[j];
        }

/*
        // merge方法体流程!
        System.out.print("方法执行:");
        for (int i1 : help) {
            System.out.print(i1+" ");
        }
        System.out.println();
*/

    }


    public static void main(String[] args) {
        MergeSortTest mergeSortTest = new MergeSortTest();
        int arr[] = new int[]{11,8,9,4,12,3,7,6};
        System.out.println("原数据:"+ "11,8,9,4,12,3,7,6");
        mergeSortTest.process(arr,0,arr.length-1);
        System.out.print("输出结果:");
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }



    // 规范


}
